"""
Geometric objects for collision detection, boundary definition, etc.
"""

import math


class UnknownColliderType(Exception):
	""" Raised when a shape doesn't know how to collide. """
	def __init__(self, collider):
		Exception.__init__(self)
		self.collider = collider

class Point(object):
	""" Simple 2D point. """
	x = 0.0
	y = 0.0
	def __init__(self, x=0, y=0, klass=None):
		if klass is not None:
			self.x = klass(x)
			self.y = klass(y)
		else:
			self.x = float(x)
			self.y = float(y)
	
	@staticmethod
	def fromVector(angle, dist):
		""" Create a new vector from an angle and magnitude. """
		deltaY = math.sin(angle) * dist
		deltaX = math.cos(angle) * dist
		return Point(deltaX, deltaY)
	
	length = property(lambda self: math.hypot(self.x, self.y) )
	tuple  = property(lambda self: (self.x, self.y) )
	pos    = property(lambda self: (int(self.x), int(self.y)) )
	loc    = property(lambda self: (int(10 * round(self.x, 1)),
								int(10 * round(self.y, 1)) ))
	floor  = property(lambda self: Point(math.floor(self.x),
										math.floor(self.y)) )
	flip   = property(lambda self: Point(self.y, self.x))
	sum    = property(lambda self: self.x + self.y)

	def round(self, places=0):
		""" Round off our coordinates to the nearest 10**-places
			and return a new Point. """
		return Point(round(self.x, places),
					round(self.y, places))
	
	def angle(self):
		""" Our angle relative to the positive x-axis. """
		return math.atan2(self.y, self.x)
	
	def dist(self, other):
		""" The euclidean distance betwixt us and other. """
		delta = other - self
		return math.hypot(delta.x, delta.y)
	
	def __str__(self):
		return 'Pt(%s, %s)' % (self.x, self.y)
	
	def __repr__(self):
		return 'Point(%s, %s)' % (self.x, self.y)

	# Various mathemagical operations    
	def __add__(self, other):
		if hasattr(other, 'dir') and hasattr(other,  'dist'):
			oth = Point.fromVector(other.angle.radians(), other.dist)
			return Point(self.x + oth.x, self.y + oth.y)
		elif hasattr(other, 'x') and hasattr(other, y):
			return Point(self.x + other.x, self.y + other.y)
		else:
			return Point(self.x + other, self.y + other)
	
	def __sub__(self, other):
		try:
			return Point(self.x - other.x, self.y - other.y)
		except AttributeError:
			return Point(self.x - other, self.y - other)
		
	def __mul__(self, other):
		try:
			return Point(self.x * other.x, self.y * other.y)
		except AttributeError:
			return Point(self.x * other, self.y * other)
		
	def __div__(self, other):
		try:
			return Point(self.x / other.x, self.y / other.y)
		except AttributeError:
			return Point(self.x / other, self.y / other)
		
	def __abs__(self):
		return Point(abs(self.x), abs(self.y))
	
	def __eq__(self, other):
		return self.x == other.x and self.y == other.y
	
	def __gt__(self, other):
		return (self.x > other.x) or (self.x == other.x and self.y > other.y)
	
	def __ge__(self, other):
		return (self.x > other.x) or (self.x == other.x and self.y >= other.y)
	
	def __lt__(self, other):
		return (self.x < other.x) or (self.x == other.x and self.y < other.y)
	
	def __le__(self, other):
		return (self.x < other.x) or (self.x == other.x and self.y <= other.y)
	
	def __eq__(self, other):
		return self.x == other.x and self.y == other.y
	

class AxisAlignedBoundingBox(object):
	"""
	A location defined by a isothetic rectangle.
	
	Always an exact point or larger. (i.e. max >= min).
	"""
	
	(AB_CENTER,
	AB_TOPLEFT,
	AB_TOPRIGHT,
	AB_BOTTOMRIGHT,
	AB_BOTTOMLEFT) = range(5)
	
	def __init__(self, minX, minY, maxX=None, maxY=None):
		if type(minX) is Point and type(minY) is Point:
			maxX, maxY = minY.pos
			minX, minY = minX.pos
		
		self._min = Point(min(minX, maxX), min(minY, maxY))
		self._max = Point(max(minX, maxX), max(minY, maxY))
	
	def __hash__(self):
		return eval('%s+%sj' % (hash(self.min), hash(self.max)) )

	min = property(lambda self: self._min)    
	max = property(lambda self: self._max)
	bottomleft = property(lambda self: Point(self._min.x, self._max.y))
	topright = property(lambda self: Point(self._max.x, self._min.y))
	center = property(lambda self: self._min + self.radii)
	angle = property(lambda self: 0.0)
	radii = property(lambda self: self.size / 2.0)
	size = property(lambda self: self._max - self._min)

	def translate(self, delta):
		"""
		Move this box by Point <delta>, and return
		the new AABB.
		"""
		newMin = self._min + delta
		newMax = self._max + delta
		return AxisAlignedBoundingBox(newMin.x, newMin.y,
									newMax.x, newMax.y)
	
	def enumerate(self):
		"""
		Yield a sequence of tuples, one for each
		integral coordinate contained herein.
		"""
		for x in range(self.min.x, self.max.x+1):
			for y in range(self.min.y, self.max.y+1):
				yield (x, y)
	
	def rotate(self, quarters, about=AB_CENTER):
		"""
		Rotate this box by <quarters> x 90 degrees,
		about <about>, and return the new AABB.
		"""
		quarters = quarters % 4
		if quarters == 0:
			return self
		
		if about == self.AB_CENTER:
			rel = self.center
		elif about == self.AB_TOPLEFT:
			rel = self.min
		elif about == self.AB_TOPRIGHT:
			rel = self.topright
		elif about == self.AB_BOTTOMRIGHT:
			rel = self.max
		elif about == self.AB_BOTTOMLEFT:
			rel = self.bottomleft
			
		newMin = self._min - rel
		newMax = self._max - rel
		
		if 0 < quarters < 3:
			negX = Point(-1.0, 1.0)
			newMin *= negX
			newMax *= negX
			
		if quarters > 1:
			negY = Point(1.0, -1.0)
			newMin *= negY
			newMax *= negY
			
		if quarters in (1, 3):
			newMin = newMin.flip
			newMax = newMax.flip
			
		newMin += rel
		newMax += rel
		return AxisAlignedBoundingBox(newMin.x, newMin.y, newMax.x, newMax.y)

	def containsPoint(self, other):
		"""
		Test for collision with the point <other>.
		"""
		return (self.min.x <= other.x and
				other.x <= self.max.x and
				self.min.y <= other.y and
				other.y <= self.max.y)

	def overlapsBox(self, other):
		"""
		Test for collision with the AABB <other>.
		"""
		if (other.min.x > self.max.x or
			other.min.y > self.max.y or
			other.max.x < self.min.x or
			other.max.y < self.min.y):
			return False
		return True
	
	def containsBox(self, other):
		"""
		Test for complete containment of AABB <other>.
		"""
		if (not self.overlapsBox(other) or
			other.max.x > self.max.x or
			other.min.y < self.min.y or
			other.max.y > self.max.y or
			other.min.x < self.min.x):
			return False
		return True
	
	def collision(self, other):
		"""
		Test for collision with another shape.
		"""
		if hasattr(other, 'x'):
			# Point
			return self.containsPoint(other)
		elif hasattr(other, '_radii'):
			# Oriented
			return other.overlapsBox(self)
		elif hasattr(other, 'radii'):
			# Axis Aligned
			return self.overlapsBox(other)
		elif hasattr(other, 'radius'):
			# Circle
			return other.overlapsBox(self)
		
		raise UnknownColliderType(other)
		
		
	def dist(self, other):
		"""
		Return the euclidean distance between
		this object and <other>.
		"""
		# Note: Left and Right and Top and Bottom
		#       in the comments assume x increases to the right
		#       and y increases downward.
		#       This has no effect on the algorithm.
		#       Just pretend they're pixels on a screen.
		distance = None
		
		if hasattr(other, 'x'):

			# Depending on which of the 9 categories it falls into,
			# compare it to an edge or a corner.
			if other.x < self.min.x:

				# To the left of us
				if other.y < self.min.y:
					# Above and left of us
					distance =  self.min.dist(other)

				elif other.y <= self.max.y:
					# To the left of us, between top and bottom
					# Perpendicular distance to the left edge
					distance =  self.min.x - other.x

				else:
					# Below and to the left
					distance =  self.bottomleft.dist(other)
					
			elif other.x <= self.max.x:
				# Between the left and right
				if other.y < self.min.y:
					# Above us
					# Perpendicular distance to top edge
					distance =  self.min.y - other.y
				
				elif other.y <= self.max.y:
					# Inside us
					distance =  0.0
				
				else:
					# Below us
					# Perpendicular distance to bottom edge
					distance =  other.y - self.max.y
			
			else:
				# Above the top on the right
				if other.y < self.min.y:
					# Above and left of us
					distance =  self.topright.dist(other)
				
				elif other.y <= self.max.y:
					# To the right of us, between top and bottom
					# Perpendicular distance to right edge
					distance =  other.x - self.max.x
				
				else:
					# Below and to the right
					distance =  self.max.dist(other)
				
		elif hasattr(other, 'min'):
			# Other is another BoundingBox instance
			# (or at least pretending)
			
			if other.max.x < self.min.x:
				# To the left of us
				
				if other.max.y < self.min.y:
					# Above us
					distance =  self.min.dist(other.max)
				
				elif other.min.y <= self.max.y:
					# Beside us
					# Perpendicular distance between near edges
					distance =  self.min.x - other.max.x
				
				else:
					# Below us
					distance =  self.bottomleft.dist(other.topright)
					

			elif other.min.x <= self.max.x:
				# Above, overlapping, or below us

				if other.max.y < self.min.y:
					# Above us
					distance =  self.min.y - other.max.y
				
				elif other.min.y <= self.max.y:
					# Overlapping
					distance =  0.0
				
				else:
					# Below us
					distance =  other.min.y - self.max.y

			
			else:
				# To the right of us

				if other.max.y < self.min.y:
					# Above us
					distance =  self.topright.dist(other.bottomleft)
				
				elif other.min.y <= self.max.y:
					# Beside us
					# Perpendicular distance between near edges
					distance =  other.min.x - self.max.x
				
				else:
					#Below us
					distance =  self.max.dist(other.min)
			

		elif hasattr(other, '_radii'):
			distance = other.dist(self)
		
		if distance is None:
			raise UnknownColliderType(other)
		
		return distance
		
	def __eq__(self, other):
		return self.min == other.min and self.max == other.max

	def __str__(self):
		return "BoundingBox( %s - %s )" % (str(self.min), str(self.max))

	def __repr__(self):
		return "BoundingBox( %0.2f, %0.2f, %0.2f, %0.2f )" % (self.min.x,
															self.min.y,
															self.max.x,
															self.max.y)


class OrientedBoundingBox(object):
	"""
	A location defined by a non-isothetic rectangle
	(non-axis-aligned bounding box).
	"""
	_angle = 0
	_radii = Point(0.0, 0.0)
	_center = Point(0.0, 0.0)
	
	def __init__(self, center, size, angle):
		self._center = center
		self._radii = size / 2
		self._angle = angle
		
	angle = property((lambda self: self._angle))
	radii = property((lambda self: self._radii))
	size = property((lambda self: self._radii*2))
	center = property((lambda self: self._center))

	def translation(self, other):
		"""
		Return a Point object containing the
		distance (translation) between this
		object's center and the other's center.
		"""
		return self._center - other.center
	
	def translate(self, delta):
		"""
		Move the center box by Point <delta>, and
		return the new OBB.
		"""
		return OrientedBoundingBox(self._center + delta,
								self.size,
								self._angle)
	
	def rotate(self, angle):
		"""
		Return a new OBB with the same center
		and size as this object, but rotated
		by an additional <angle>.
		"""
		return OrientedBoundingBox(self._center,
								self.size,
								self._angle + angle)
	
	def rotation(self, other):
		"""
		Return the angular rotation difference
		between this object and <other>.
		"""
		return self._angle - other.angle
	
	# Reduced version of overlapsBox 
	def containsPoint(self, other):
		"""
		Test whether we collide with Point <other>.
		"""
		# retrieve the relative translation
		translation = self._center - other
		# drop translation onto our X and Y vectors to make sX and sY
		distOther = abs(Point.fromVector(translation.angle() - self._angle,
										translation.length))
		
		# check sX (T on x)
		if (distOther.x > self._radii.x):
			return False

		# check sY (T on y)
		if (distOther.y > self._radii.y):
			return False

		return True
		
	# From Stefan Gottschalk's
	#    "Collision Queries using Oriented
	#       Bounding Boxes" (2000)
	# http://citeseer.ist.psu.edu/336883.html
	def overlapsBox(self, other):
		"""
		Test whether we collide with an AABB or OBB <other>.
		"""
		# retrieve the relative translation
		translation = self.translation(other)
		srad = self._radii
		orad = other.radii
		# do the cosine for dot products once.
		rot = abs(Point.fromVector(self.rotation(other), 1))

		# drop translation onto our X and Y vectors to make sX and sY
		distOther = abs(Point.fromVector(translation.angle() - self._angle,
										translation.length))
		
		# check sX (T on x)
		if (distOther.x > srad.x + rot.x * orad.x + rot.y * orad.y):
			return False

		# check sY (T on y)
		if (distOther.y > srad.y + rot.y * orad.x + rot.x * orad.y):
			return False

		# Check in reverse
		translation *= Point(-1.0, -1.0)
		distSelf = abs(Point.fromVector(translation.angle() - other.angle,
										translation.length))

		# check sX (T on x)
		if (distSelf.x > orad.x + rot.x * srad.x + rot.y * srad.y):
			return False

		# check sY (T on y)
		if (distSelf.y > orad.y + rot.y * srad.x + rot.x * srad.y):
			return False

		return True
	
	def dist(self, other):
		"""
		Return the euclidean distance between
		this object and <other>.
		"""
		
		if hasattr(other, 'x'):
			# Point distance.

			# retrieve the relative translation
			translation = self._center - other
			# drop translation onto our X and Y vectors to make sX and sY
			distOther = abs(Point.fromVector(translation.angle() - self._angle,
											translation.length))

			return max(distOther.x - self._radii.x,
					distOther.y - self._radii.y)

		elif hasattr(other, 'radii'):
			# AABB or OBB distance.
			srad = self._radii
			orad = other.radii
			# do the cosine for dot products once.
			rot = abs(Point.fromVector(self.rotation(other), 1))
	
			# drop translation onto our X and Y vectors to make sX and sY
			translation = self.translation(other)
			distOther = abs(Point.fromVector(translation.angle() - self._angle,
											translation.length))
			translation *= Point(-1.0, -1.0)
			distSelf = abs(Point.fromVector(translation.angle() - other.angle,
											translation.length))
			
			# find the highest penetration on all projections
			return max(
				distOther.x - srad.x - rot.x * orad.x - rot.y * orad.y,
				distOther.y - srad.y - rot.y * orad.x - rot.x * orad.y,
				distSelf.x - orad.x - rot.x * srad.x - rot.y * srad.y,
				distSelf.y - orad.y - rot.y * srad.x - rot.x * srad.y
				)
		
	def collision(self, other):
		"""
		Test whether this object collides with
		{Point,AABB,OBB} <other>.
		"""

		if hasattr(other, 'x'):
			# Point
			return self.containsPoint(other)
		elif hasattr(other, 'radii'):
			# OBB or AABB
			return self.overlapsBox(other)
		
		elif hasattr(other, 'radius'):
			return other.overlapsBox(self)
		
		raise UnknownColliderType(other)


class BoundingCircle(object):
	
	def __init__(self, center, radius):
		self._center = center
		self._radius = radius
	
	radius = property(lambda self: self._radius)    
	center = property(lambda self: self._center)

	def collision(self, other):
		"""
		Test whether this object collides with
		{Point,AABB,OBB,Circle} <other>.
		"""

		if hasattr(other, 'radius'):
			return self.overlapsCircle(other)
		elif hasattr(other, 'radii'):
			return self.overlapsBox(other)
		elif hasattr(other, 'x'):
			return self.containsPoint(other)
		
		raise UnknownColliderType(other)

	def containsPoint(self, other):
		"""
		Test whether this object collides with
		Point <other>.
		"""
		translation = abs(self._center - other)
		if translation.length > self._radius:
			return False
		return True
	
	def overlapsCircle(self, other):
		"""
		Test whether this object collides with
		BoundingCircle <other>.
		"""
		# Only a single axis of separation is necessary.
		translation = abs(self._center - other.center)
		if translation.length > self._radius + other.radius:
			return False
		return True
	
	# According to:
	#   http://www.harveycartel.org/metanet/tutorials/tutorialA.html#section3
	# we can skip the third projection if our center is closest
	# to a AABB edge, instead of an AABB vertex.  Unfortunately, 
	# that won't work for OBB's.
	def overlapsBox(self, other):
		"""
		Test whether this object collides with
		{AABB,OBB} <other>.
		"""
		# Three axes of separation.
		
		# retrieve the relative translation
		translation = abs(self._center - other.center)
		rot = Point.fromVector(other.angle, 1)
		
		# check sX (T on x)
		if translation.x > (other.radii * rot).sum + self._radius:
			return False

		# check sY (T on y)
		if translation.y > (other.radii * rot.flip).sum + self._radius:
			return False

		
		# check sR (T on t)
		rot = Point.fromVector(translation.angle() - other.angle,
							1)
		if translation.length > (other.radii * rot).sum + self._radius:
			return False

		return True


#utility function for BoundingPoly
def isLeft(point, line):
	"""
	Test horizontal location of a point relative to the given 
	line (or tuple of two points).
	Returns:
		>0 for point is left of the line,
		=0 for point is on the line, and
		<0 for point is right of the line.
	"""
	p0, p1, p2 = line[0], line[2], point
	return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y)

class BoundingPoly(object):
	pa = ()
	def __init__(self, pa):
		"""
		pa: An array of points that defines the edges of this polygon. May
		or may not have the last point be the same as the first point.
		"""
		finishPoly = (pa[0] != pa[-1])
		self.pa = pa
		if self.finishPoly:
			self.pa.append(self.pa[0])
		
	def collision(self, other):
		if hasattr(other, 'radius'):
			return self.overlapsCircle(other)
		elif hasattr(other, 'radii'):
			return self.overlapsBox(other)
		elif hasattr(other, 'x'):
			return self.containsPoint(other)
		elif hasattr(other, 'pa'):
			return self.overlapsPoly(other)
		
		raise UnknownColliderType(other)
		
	def containsPoint(self, other):
		"""
		Uses the winding count method, as given on:
		http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
		"""
		wn = 0
		for i in range( len(self.pa) - 1 ):
			if self.pa[i].y <= other.y:
				if self.pa[i+1].y > other.y:
					if isleft(other, (self.pa[i], self.pa[i+1]) ) > 0:
						wn += 1
			else:
				if self.pa[i+1].y <= other.y:
					if isLeft( other, (self.pa[i], self.pa[i+1]) ) < 0:
						wn -= 1
		return wn != 0
	
	def overlapsCircle(self, other):
		pass
	
	def overlapsBox(self, other):
		pass
	
	def overlapsPoly(self, other):
		#http://www.geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm
		#seems to have good information, but I currently do not know how and do not
		#need to figure out how to implement the suggestions given there. I think the
		#best option is a slight adaptation on psuedo-code for the Shamos-Hoey algo.
		#Currently, though, only need to intersect points.
		pass
	
if __name__ == "__main__": # pylint: block-disable-msg
	#Test the AxisAlignedBoundingBox.rotate
	abBox = AxisAlignedBoundingBox(Point(0, 0), Point(10, 10))
	#print abBox.rotate(1, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
	#print abBox.rotate(2, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
	#print abBox.rotate(3, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
	#print abBox.rotate(4, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
	#print
	#
	
	# Test the BoundingCircle.collision
	obBox = OrientedBoundingBox(Point(10.0, 10.0),
								Point(1.0,1.0), math.pi / 4)
	cBound = BoundingCircle(Point(12.0, 12.0), 2.825)
	print abBox.collision(cBound)

